﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

/* The problem is to find whether 2 objects (nodes) in a network are connected.
 * Lets consider there are N nodes in a network. This can be positioned in an array
 * from 0 to N-1.
 * Algorithms 
 * 1. Quick Find
 * 2. Quck Union
 * 3. Weighted Quck Union
 * 4. Path Compression
 *  
 */

namespace Demo.Framework.Algorithms.UnionFind
{
    //class Union
    //{
    //    private int[] _node;
    //    private int _arrayCount;

    //    public Union(int N)
    //    {
    //        _arrayCount = N;
    //        _node = new int[_arrayCount];

    //        for (int i = 0; i < _arrayCount; i++)
    //        {
    //            _node[i] = i;
    //        }
    //    }

    //    /// <summary>
    //    /// Quick Find - Time complexity - O(1)
    //    /// If 2 nodes, p and q, are connected, then the elemnet of the array 
    //    /// at p and q will be equal.  array[p] = array[q]
    //    /// i.e they belong to the same connected set
    //    /// </summary>
    //    /// <param name="p"></param>
    //    /// <param name="q"></param>
    //    /// <returns></returns>
    //    public bool IsConnected(int p, int q)
    //    {
    //        return _node[p] == _node[q];
    //    }

    //    /// <summary>
    //    /// The union function for Quick Time
    //    /// Union(p,q) = p,q now should belong to the same set.
    //    /// Find all elements array[i] == array[p]
    //    /// Set each array[i] = array[q]
    //    /// Time Complexity - O(n2) - If each node is separate and has to be connected to the other
    //    /// </summary>
    //    /// <param name="p"></param>
    //    /// <param name="q"></param>
    //    /// <returns></returns>
    //    public bool Union(int p, int q)
    //    {
    //        try
    //        {
    //            for (int i = 0; i < _arrayCount; i++)
    //            {
    //                if (_node[i] == _node[p])
    //                {
    //                    _node[i] = _node[q];
    //                }
    //            }
    //            return true;
    //        }
    //        catch (Exception)
    //        {

    //            return false;
    //        }
    //    }

    //    /// <summary>
    //    /// Find the root of a node
    //    /// </summary>
    //    /// <param name="i"></param>
    //    /// <returns></returns>
    //    private int Root(int i)
    //    {
    //        while (i != _node[i])
    //        {
    //            i = _node[i];
    //        }

    //        return _node[i];
    //    }

    //    public bool IsConnected(int p, int q)
    //    {
    //        return Root(p) == Root(q);
    //    }

    //    /// <summary>
    //    /// Quick Union - Complexity O(N)
    //    /// The nodes are now in a tree with each elemnt storing the parent
    //    /// For ex, if p's parent = q, then array[p] = q.
    //    /// If p is a root, array[p]= p.
    //    /// Union (p,q) = Set root(p) = root(q)
    //    /// Detect root(q). Find root(p). root(p) resides in array[root(p)].
    //    /// array[root(p)] = root(q)
    //    /// </summary>
    //    /// <param name="p"></param>
    //    /// <param name="q"></param>
    //    /// <returns></returns>
    //    public bool Union(int p, int q)
    //    {
    //        try
    //        {
    //            // find root of q
    //            // set root of p as root of q
    //            int root_p = Root(p);
    //            _node[root_p] = Root(q);
    //            return true;
    //        }
    //        catch (Exception)
    //        {
    //            return false;
    //        }            
    //    }

    //    /// <summary>
    //    /// Weighted quick union - Time Complexity O(Log 2 N)
    //    /// The idea is to add two nodes, such that the tree is balanced.
    //    /// Union (p, q) = If p , q are isolated nodes, set root(p) = root(q)
    //    /// Else, if p belongs to a larger tree, put smaller tree (containing q) 
    //    /// under tree of p and vice versa
    //    /// For a addition, the max height of the tree can increase by only two.
    //    /// So, for N elements, the naximum number of times that can happen = Log 2 N
    //    /// </summary>
    //    /// <param name="p"></param>
    //    /// <param name="q"></param>
    //    /// <returns></returns>
    //    public bool Union(int p, int q)
    //    {
    //        try
    //        {
    //            int root_q = Root(q);
    //            int root_p = Root(p);

    //            if (Depth(p) > Depth(q))
    //            {
    //                // put q under P
    //                _node[root_q] = root_p;
    //            }
    //            else
    //            {
    //                _node[root_p] = root_q;
    //            }

    //            return true;
    //        }
    //        catch (Exception)
    //        {                
    //            return false;
    //        }
    //    }

    //    /// <summary>
    //    /// 
    //    /// </summary>
    //    /// <param name="p"></param>
    //    /// <returns></returns>
    //    private int Depth(int i)
    //    {
    //        int depth = 0;
    //        while (i != _node[i])
    //        {
    //            i = _node[i];
    //            depth++;
    //        }
    //        return depth + 1;
    //    }
    //}
}
